Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ich hatte ja schon mal angekündigt, dass wir uns mit dem dualen Simplex beschäftigen wollen

und noch ein, zwei Varianten, die gucken wir uns heute und morgen an.

Und letzte Woche haben wir ja sozusagen den Rest abgeschlossen,

also sprich, wie implementiert man das Simplex-Verfahren.

Da habe ich auch noch die Spitze des Eisbergs ein bisschen angeguckt,

weil ich hoffe, Sie haben ein bisschen den Eindruck gekriegt,

dass zwischen einer Implementierung und einer Implementierung da durchaus ein Unterschied sein kann

und dass es da durchaus sehr, sehr viele Tricks gibt,

wie man diese fünf Schritte sehr effizient hinbekommt.

Und da ist wirklich auch, wenn man in die praktischen Tools guckt, die es dazu gibt, enorme Unterschiede.

Da kommt auch alle paar Jahre, ich glaube alle zwei, drei Jahre in ORMS Today,

die Hauptzeitschrift von Informs in den USA, immer so eine Übersicht raus über aktuelle LP-Löser

und was die so alles können.

Und wer da mal Interesse hat, kann da durchaus mal reingucken,

oder später, wenn Sie mal irgendwo in der Firma sind und Sie müssen tatsächlich einen LP lösen,

oder vermutlich dann eher ein ganzzahliges Problem,

was wir uns später ja noch angucken wollen in einer anderen Vorlesung,

dann kriegt man da einen ganz netten Überblick, was es gerade so an aktueller Software gibt

und wie die zum Teil performen.

Gibt es zur letzten Woche noch Fragen?

Gut, wenn nicht, dann würden wir heute den Dual machen, den sollten wir glaube ich einigermaßen durchkriegen.

Und es gibt noch ein zweites Verfahren, die Behandlung von oberen Schranken unter den oberen Schranken,

das schauen wir uns noch ein bisschen an, vielleicht machen wir auch ein bisschen Handwafing,

weil wir morgen natürlich dann noch ein Stück die Evaluationsergebnisse besprechen,

da wäre es vielleicht ganz nett, also Wink in die Kamera,

wenn der eine oder die andere hinter der Kamera vielleicht morgen dann nochmal käme,

damit wir die Vorlesung besprechen können, was gut war, was schlecht war,

und vor allem was man halt besser machen kann für die nächsten Semestern.

Und dann würde ich noch morgen auch noch einen kleinen Ausblick geben,

was gibt es denn danach, nach der kombinatorischen Optimierung,

was steht denn im Bachelor-Master-Bereich sonst noch an möglichen Fortsetzungen dieser Vorlesungen.

Gut, also wir wollen uns mit Varianten beschäftigen, die erste ist der Duale Simplex,

der ursprünglich, als das in den 50ern entwickelt wurde, man zunächst glaubte,

man hatte ein komplett anderes Verfahren, wie sich aber später herausstellte,

ist es nichts anderes als das Primale, dann sogenannten Primal,

oder die Grundversion, die wir kennengelernt haben, angewendet auf das Duale Programm.

Und wenn man das alles richtig interpretiert und die unnötigen Redundanzen,

wie wir gleich sehen werden, weglässt, dann kommt tatsächlich eine interessante Alternative heraus,

wie man lineare Programme lösen kann, und wir werden das uns anschauen, ohne dass wir explizit dualisieren.

Wie wir gleich sehen werden, das Duale selbst kann dann, wenn man es in seiner Standardform anschaut,

sehr groß werden, aber wir werden das dann rückinterpretieren auf der primalen Seite

und dann sehen, dass wir dadurch durchaus eine Alternative kriegen.

Die Alternative hatte ich schon mal angedeutet, damals, als wir uns die Grundversion vom Simplex angeguckt haben,

nämlich was das Simplex-Verfahren macht, ist, man hat eine primal zulässige Basis,

man hat Optimalität, also den komplementären Schlupf eingehalten,

und man zielt darauf ab, die Dualvariate entspricht, das Y zulässig zu kriegen.

Das duale Simplex-Verfahren fungiert genau umgekehrt, wir fangen mit einer dual zulässigen Lösung an,

wir halten wieder den komplementären Schlupf ein und hoffen, oder unser Ziel ist, primal zulässig zu werden.

Und genau dieses Konzept hat man ja auch schon bei zum Beispiel Mincos Flow-Algorithmen,